package com.lixianbiao;

/**
 * 斐波那契数列
 *
 * @author lixianbiao
 * @since 2024/06/04 14:51
 */
public class FibonacciNumber {
    // 递归实现
    public static long functionV1(int n) throws IllegalArgumentException {
        // 递归边界
        if (n < 0) {
            throw new IllegalArgumentException();
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return functionV1(n - 1) + functionV1(n - 2);
    }

    // 动态规划实现
    public static long functionV2(int n) throws IllegalArgumentException {
        if (n < 0) {
            throw new IllegalArgumentException();
        }
        //dp数组
        long[] dp = new long[n+1];
        //初始化
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 2; i < n; i++) {
            //存储中间结果，并利用中间结果计算
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 优化dp数组
    public static long functionV3(int n) throws IllegalArgumentException {
        if (n < 0) {
            throw new IllegalArgumentException();
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int p = 1;
        int q = 1;
        int r = 0;
        for(int i = 3; i <= n; i++){
            // 1,1,0
            r = p+q;
            // 1,1,2---->1,2,r
            p = q;
            q = r;
        }
        return r;
    }

    public static void main(String[] args) throws IllegalArgumentException {
        long start = System.currentTimeMillis();
        System.out.println("functionV1(45) = " + functionV1(45));
        long end = System.currentTimeMillis();
        System.out.println(((end - start) / 1000) + "秒");
        System.out.println("=================================");
        start = System.currentTimeMillis();
        System.out.println("functionV2(45) = " + functionV2(45));
        end = System.currentTimeMillis();
        System.out.println(((end - start) / 1000) + "秒");
       /* System.out.println("=================================");
        start = System.currentTimeMillis();
        System.out.println("functionV3(45) = " + functionV3(45));
        end = System.currentTimeMillis();
        System.out.println(((end - start) / 1000) + "秒");*/
    }
}